import java.util.HashMap;
import java.util.LinkedList;

import java.util.*;
public class LRUPageReplacement {

    public static void main(String[] args) {

        int[] pageRequests = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

        int numFrames = 4;
        List<Integer> frames = new ArrayList<>();

        Map<Integer, Integer> frameMap = new HashMap<>();

        int pageFaults = 0;

        int totalPageAccesses = pageRequests.length;

        int successfulAccesses = 0;



        for (int page : pageRequests) {

            boolean pageFound = frames.contains(page);

            System.out.print("当前页面请求: " + page + " | ");

            System.out.print("当前帧内容: " + frames + " | ");



            if (!pageFound) {

                if (frames.size() < numFrames) {

                    frames.add(page);

                    frameMap.put(page, frameMap.size() + 1); // 使用 size + 1 作为时间戳模拟

                    System.out.println("页面 " + page + " 被添加到帧中 -> " + frames);

                } else {

                    int leastRecent = Integer.MAX_VALUE;

                    int replacePage = -1;

                    for (int i = 0; i < frames.size(); i++) {

                        int framePage = frames.get(i);

                        if (frameMap.get(framePage) < leastRecent) {

                            leastRecent = frameMap.get(framePage);

                            replacePage = i;

                        }

                    }

                    frames.set(replacePage, page);

                    frameMap.remove(frames.get(replacePage)); // 旧的被替换页面

                    frameMap.put(page, frameMap.size() + 1); // 使用 size + 1 作为时间戳模拟（这里不准确但可行）

                    System.out.println("页面 " + frames.get(replacePage) + " 被替换为 " + page + " -> " + frames);

                }

                pageFaults++;

            } else {

                frameMap.put(page, frameMap.size() + 1); // 更新最近访问时间（不准确但可行）

                System.out.println("页面 " + page + " 已在帧中");

                successfulAccesses++;

            }
            // 输出分隔线
            for (int i = 0; i < 50; i++) {
                System.out.print("-");
            }
            System.out.println();
        }

        // 计算页面命中率

        double pageHitRate = (double) successfulAccesses / totalPageAccesses;

        System.out.println("\n最终帧内容: " + frames);

        System.out.println("LRU页面中断次数：" + pageFaults);

        System.out.println("LRU页面命中率：" + (pageHitRate * 100) + "%");

    }

}